#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_set"

using namespace std;
/*HJJ QQ479287006
 *给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

 

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。
示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//TODO 首先能想到的这个是 回溯法解决吧 然而超时 需要使用记忆化回溯
//bool wordBreakBack(string& s, vector<string>& wordDict ,string nowStr,int index)
//{
// 我擦我这个回溯很慢啊 超级慢了跟人家不用记忆化回溯都慢
//    if (s.compare(nowStr)==0)
//        return true;
//    if (s.size()<nowStr.size())
//        return false;
//
//    for (int i = index; i <wordDict.size() ; ++i) {
//        if (wordBreakBack(s,wordDict,nowStr+wordDict[i],i+1))
//            return true;
//    }
//
//    return false;
//
//}
//bool wordBreak(string s, vector<string>& wordDict) {
//
//    return wordBreakBack(s,wordDict,"",0);
//}

//他这个是循环 s 给出的字符串 我循环的是数组
//bool backtracking(const string &s, const unordered_set<string> &wordSet,
//                  int startIndex) {
//
//    if (startIndex >= s.size()) {
//        return true;
//    }
//
//
//    for (int i = startIndex; i < s.size(); i++) {
//        string word = s.substr(startIndex, i - startIndex + 1);
//        //todo 这个我还真有可能写不出来wordSet.find(word) != wordSet.end()
//        if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet,i + 1)) {
//            return true;
//        }
//
//    }
//    return false;
//}
//
//bool wordBreak(string s, vector<string> &wordDict) {
//    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
//    return backtracking(s, wordSet, 0);
//}


//bool backtracking(const string &s,
//                  const unordered_set<string> &wordSet,
//                  vector<int> &memory,
//                  int startIndex) {
//    if (startIndex >= s.size()) {
//        return true;
//    }
//    // 如果memory[startIndex]不是初始值了，直接使⽤memory[startIndex]的结果 //蒙蔽
//    if (memory[startIndex] != -1) return memory[startIndex];
//    for (int i = startIndex; i < s.size(); i++) {
//        string word = s.substr(startIndex, i - startIndex + 1);
//        if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet,memory, i + 1)) {
//            memory[startIndex] = 1; // 记录以startIndex开始的⼦串是可以被拆分的
//            return true;
//        }
//    }
//    memory[startIndex] = 0; // 记录以startIndex开始的⼦串是不可以被拆分的
//    return false;
//}
//
//bool wordBreak(string s, vector<string> &wordDict) {
//    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
//    vector<int> memory(s.size(), -1); // -1 表示初始化状态
//    return backtracking(s, wordSet, memory, 0);
//}
//

//TODO  不太懂
//单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满.
//递推shizi dp[i]表示是否可以 dp[i]&&dp[]
bool wordBreak(string s, vector<string> &wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;

    //背包是s的长度
    for (int i = 1; i <= s.size(); i++) { // 遍历背包

        for (int j = 0; j < i; j++) { // 遍历物品
            string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
            if (wordSet.find(word) != wordSet.end() && dp[j]) {
                dp[i] = true;
            }
        }

    }


    // return dp[s.size()];
}


bool wordBreak1(string s, vector<string> &wordDict) {
    wordDict.emplace(wordDict.begin(), "0");
    s.insert(s.begin(), '0');
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    vector <vector<bool>> dp(s.size(), vector<bool>(wordDict.size(), false));



    //先背包size 后物品
    for (int j = 0; j <= s.size(); ++j) {
        dp[0][j] = true;
    }

    for (int j = 0; j <= wordDict.size(); ++j) {
        dp[j][0] = true;
    }


    //背包大小 先背包后物品
    for (int i = 1; i < s.size(); ++i) {
        //物品大小
        for (int j = 1; j < wordDict.size(); ++j) {

        }

    }


    return dp[s.size()][wordDict.size()];

    // return dp[s.size()];
}